package com.tsx.leetcode.hot100.easy;

/**
 * <a href="https://leetcode.cn/problems/climbing-stairs">爬楼梯</a>
 */
public class Q70ClimbStairs {
    public static void main(String[] args) {
        Q70ClimbStairs q70ClimbStairs = new Q70ClimbStairs();
        int res = q70ClimbStairs.climbStairs(5);
        System.out.println("res = " + res); // 8
    }

    /**
     * 爬N阶台阶就等于爬N-1阶+1
     *
     * @param n
     * @return
     */
    public int climbStairs(int n) {
        if (n == 1) {
            return 1;
        }
        int[] dp = new int[n];
        dp[0] = 1; // Base case: 1 way to climb 1 step
        dp[1] = 2; // Base case: 2 ways to climb 2 steps
        for (int i = 2; i < dp.length; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n - 1];
    }
}
